//2369. 检查数组是否存在有效划分

//给你一个下标从 0 开始的整数数组 nums ，你必须将数组划分为一个或多个 连续 子数组。
//如果获得的这些子数组中每个都能满足下述条件 之一 ，则可以称其为数组的一种 有效 划分：
//子数组 恰 由 2 个相等元素组成，例如，子数组[2, 2] 。
//子数组 恰 由 3 个相等元素组成，例如，子数组[4, 4, 4] 。
//子数组 恰 由 3 个连续递增元素组成，并且相邻元素之间的差值为 1 。例如，子数组[3, 4, 5] ，但是子数组[1, 3, 5] 不符合要求。
//如果数组 至少 存在一种有效划分，返回 true ，否则，返回 false 。

//class Solution {
//public:
//    bool validPartition(vector<int>& nums) {
//        int n = nums.size();
//        vector<int> f(n + 1);
//        f[0] = true;
//        for (int i = 1; i < n; i++) {
//            if (f[i - 1] && nums[i] == nums[i - 1] ||
//                i > 1 && f[i - 2] && (nums[i] == nums[i - 1] && nums[i] == nums[i - 2] ||
//                    nums[i] == nums[i - 1] + 1 && nums[i] == nums[i - 2] + 2)) {
//                f[i + 1] = true;
//            }
//        }
//        return f[n];
//    }
//};

//39. 单词拆分

//给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。
//注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

//class Solution {
//public:
//    bool wordBreak(string s, vector<string>& wordDict) {
//        int max_len = ranges::max(wordDict, {}, &string::length).length();
//        unordered_set<string> words(wordDict.begin(), wordDict.end());
//
//        int n = s.length();
//        vector<int> memo(n + 1, -1);
//        auto dfs = [&](this auto&& dfs, int i) -> bool {
//            if (i == 0) {
//                return true;
//            }
//            int& res = memo[i];
//            if (res != -1) {
//                return res;
//            }
//            for (int j = i - 1; j >= max(i - max_len, 0); j--) {
//                if (words.count(s.substr(j, i - j)) && dfs(j)) {
//                    return res = true;
//                }
//            }
//            return res = false;
//            };
//        return dfs(n);
//    }
//};

//132. 分割回文串 II

//给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文串。
//返回符合要求的 最少分割次数 。

//class Solution {
//public:
//    int minCut(string s) {
//        int n = s.size();
//        // is_palindrome[l][r] 表示 s[l] 到 s[r] 是否为回文串
//        vector is_palindrome(n, vector<int8_t>(n), 1);
//        for (int l = n - 2; l >= 0; l--) {
//            for (int r = l + 1; r < n; r++) {
//                is_palindrome[l][r] = s[l] == s[r] && is_palindrome[l + 1][r - 1];
//            }
//        }
//
//        vector<int> f(n);
//        for (int r = 0; r < n; r++) {
//            if (is_palindrome[0][r]) { // 已是回文串，无需分割
//                continue;
//            }
//            int res = INT_MAX;
//            for (int l = 1; l <= r; l++) { // 枚举分割位置
//                if (is_palindrome[l][r]) {
//                    res = min(res, f[l - 1] + 1); // 在 l-1 和 l 之间切一刀
//                }
//            }
//            f[r] = res;
//        }
//        return f[n - 1];
//    }
//};

//2707. 字符串中的额外字符

//给你一个下标从 0 开始的字符串 s 和一个单词字典 dictionary 。你需要将 s 分割成若干个 互不重叠 的子字符串，每个子字符串都在 dictionary 中出现过。
//s 中可能会有一些 额外的字符 不在任何子字符串中。
//请你采取最优策略分割 s ，使剩下的字符 最少 。

//class Solution {
//public:
//    int minExtraChar(string s, vector<string>& dictionary) {
//        unordered_set<string> set(dictionary.begin(), dictionary.end());
//        int n = s.size();
//        vector<int> f(n + 1);
//        for (int i = 0; i < n; i++) {
//            f[i + 1] = f[i] + 1; // 不选
//            for (int j = 0; j <= i; j++) {
//                if (set.count(s.substr(j, i - j + 1))) {
//                    f[i + 1] = min(f[i + 1], f[j]);
//                }
//            }
//        }
//        return f[n];
//    }
//};

//91. 解码方法

//一条包含字母 A - Z 的消息通过以下映射进行了 编码 ：
//"1" -> 'A'
//"2" -> 'B'
//...
//"25" -> 'Y'
//"26" -> 'Z'
//然而，在 解码 已编码的消息时，你意识到有许多不同的方式来解码，因为有些编码被包含在其它编码当中（"2" 和 "5" 与 "25"）。
//例如，"11106" 可以映射为：
//"AAJF" ，将消息分组为(1, 1, 10, 6)
//"KJF" ，将消息分组为(11, 10, 6)
//消息不能分组为(1, 11, 06) ，因为 "06" 不是一个合法编码（只有 "6" 是合法的）。
//注意，可能存在无法解码的字符串。
//给你一个只含数字的 非空 字符串 s ，请计算并返回 解码 方法的 总数 。如果没有合法的方式解码整个字符串，返回 0。
//题目数据保证答案肯定是一个 32 位 的整数。

//class Solution {
//public:
//    int numDecodings(string s) {
//        int n = s.size();
//        vector<int> f(n + 1);
//        f[0] = 1;
//        for (int i = 1; i <= n; ++i) {
//            if (s[i - 1] != '0') {
//                f[i] += f[i - 1];
//            }
//            if (i > 1 && s[i - 2] != '0' && ((s[i - 2] - '0') * 10 + (s[i - 1] - '0') <= 26)) {
//                f[i] += f[i - 2];
//            }
//        }
//        return f[n];
//    }
//};

//2767. 将字符串分割为最少的美丽子字符串

//给你一个二进制字符串 s ，你需要将字符串分割成一个或者多个 子字符串  ，使每个子字符串都是 美丽 的。
//如果一个字符串满足以下条件，我们称它是 美丽 的：
//它不包含前导 0 。
//它是 5 的幂的 二进制 表示。
//请你返回分割后的子字符串的 最少 数目。如果无法将字符串 s 分割成美丽子字符串，请你返回 - 1 。
//子字符串是一个字符串中一段连续的字符序列。

//class Solution {
//public:
//    int minimumBeautifulSubstrings(string s) {
//        int n = s.size();
//        vector<int> memo(n, 0x3f3f3f3f);
//        auto isFivePower = [&](int x) -> bool {
//            while (x > 1) {
//                if (x % 5 != 0)
//                    return false;
//                x /= 5;
//            }
//            return true;
//            };
//        auto dfs = [&](this auto&& dfs, int i) -> int {
//            if (i < 0) {
//                return 0;
//            }
//            int& res = memo[i];
//            if (res != 0x3f3f3f3f) {
//                return res;
//            }
//
//            int x = 0, p = 1;
//            for (int j = i; j >= 0; j--) {
//                // [j, i]分成一组
//                x += (s[j] - '0') * p; // 十进制
//                if (s[j] == '1' && isFivePower(x)) {
//                    res = min(res, dfs(j - 1) + 1);
//                }
//                p *= 2;
//            }
//            return res;
//            };
//        int ans = dfs(n - 1);
//        return ans == 0x3f3f3f3f ? -1 : ans;
//    }
//};

//3196. 最大化子数组的总成本

//给你一个长度为 n 的整数数组 nums。
//子数组 nums[l..r]（其中 0 <= l <= r < n）的 成本 定义为：
//cost(l, r) = nums[l] - nums[l + 1] + ... + nums[r] * (−1)r − l
//你的任务是将 nums 分割成若干子数组，使得所有子数组的成本之和 最大化，并确保每个元素 正好 属于一个子数组。
//具体来说，如果 nums 被分割成 k 个子数组，且分割点为索引 i1, i2, ..., ik − 1（其中 0 <= i1 < i2 < ... < ik - 1 < n - 1），则总成本为：
//cost(0, i1) + cost(i1 + 1, i2) + ... + cost(ik − 1 + 1, n − 1)
//返回在最优分割方式下的子数组成本之和的最大值。
//注意：如果 nums 没有被分割，即 k = 1，则总成本即为 cost(0, n - 1)。

//class Solution {
//public:
//    long long maximumTotalCost(vector<int>& a) {
//        int n = a.size();
//        vector<long long> f(n + 1);
//        f[1] = a[0];
//        for (int i = 1; i < n; i++) {
//            f[i + 1] = max(f[i] + a[i], f[i - 1] + a[i - 1] - a[i]);
//        }
//        return f[n];
//    }
//};

//639. 解码方法 II

//一条包含字母 A - Z 的消息通过以下的方式进行了 编码 ：
//'A' -> "1"
//'B' -> "2"
//...
//'Z' -> "26"
//要 解码 一条已编码的消息，所有的数字都必须分组，然后按原来的编码方案反向映射回字母（可能存在多种方式）。例如，"11106" 可以映射为：
//"AAJF" 对应分组(1 1 10 6)
//"KJF" 对应分组(11 10 6)
//注意，像(1 11 06) 这样的分组是无效的，因为 "06" 不可以映射为 'F' ，因为 "6" 与 "06" 不同。
//除了 上面描述的数字字母映射方案，编码消息中可能包含 '*' 字符，可以表示从 '1' 到 '9' 的任一数字（不包括 '0'）。
//例如，编码字符串 "1*" 可以表示 "11"、"12"、"13"、"14"、"15"、"16"、"17"、"18" 或 "19" 中的任意一条消息。对 "1*" 进行解码，相当于解码该字符串可以表示的任何编码消息。
//给你一个字符串 s ，由数字和 '*' 字符组成，返回 解码 该字符串的方法 数目 。
//由于答案数目可能非常大，返回 109 + 7 的 模

//class Solution {
//private:
//    static constexpr int mod = 1000000007;
//
//public:
//    int numDecodings(string s) {
//        auto check1digit = [&](char ch) -> int {
//            if (ch == '0') {
//                return 0;
//            }
//            return ch == '*' ? 9 : 1;
//            };
//
//        auto check2digits = [&](char c0, char c1) -> int {
//            if (c0 == '*' && c1 == '*') {
//                return 15;
//            }
//            if (c0 == '*') {
//                return c1 <= '6' ? 2 : 1;
//            }
//            if (c1 == '*') {
//                if (c0 == '1') {
//                    return 9;
//                }
//                if (c0 == '2') {
//                    return 6;
//                }
//                return 0;
//            }
//            return c0 != '0' && (c0 - '0') * 10 + (c1 - '0') <= 26;
//            };
//
//        int n = s.size();
//        int a = 0, b = 1, c = 0;
//        for (int i = 1; i <= n; ++i) {
//            c = (long long)b * check1digit(s[i - 1]) % mod;
//            if (i > 1) {
//                c = (c + (long long)a * check2digits(s[i - 2], s[i - 1])) % mod;
//            }
//            a = b;
//            b = c;
//        }
//        return c;
//    }
//};

//LCR 165. 解密数字

//现有一串神秘的密文 ciphertext，经调查，密文的特点和规则如下：
//密文由非负整数组成
//数字 0 - 25 分别对应字母 a - z
//请根据上述规则将密文 ciphertext 解密为字母，并返回共有多少种解密结果。

//class Solution {
//public:
//    int crackNumber(int ciphertext) {
//        string src = to_string(ciphertext);
//        int p = 0, q = 0, r = 1;
//        for (int i = 0; i < src.size(); ++i) {
//            p = q;
//            q = r;
//            r = 0;
//            r += q;
//            if (i == 0) {
//                continue;
//            }
//            auto pre = src.substr(i - 1, 2);
//            if (pre <= "25" && pre >= "10") {
//                r += p;
//            }
//        }
//        return r;
//    }
//};

//1043. 分隔数组以得到最大和

//给你一个整数数组 arr，请你将该数组分隔为长度 最多 为 k 的一些（连续）子数组。分隔完成后，每个子数组的中的所有值都会变为该子数组中的最大值。
//返回将数组分隔变换后能够得到的元素最大和。本题所用到的测试用例会确保答案是一个 32 位整数。

//class Solution {
//public:
//    int maxSumAfterPartitioning(vector<int>& arr, int k) {
//        int n = arr.size(), f[n + 1];
//        f[0] = 0;
//        for (int i = 0; i < n; ++i) {
//            f[i + 1] = 0;
//            for (int j = i, mx = 0; j > i - k && j >= 0; --j) {
//                mx = max(mx, arr[j]);
//                f[i + 1] = max(f[i + 1], f[j] + (i - j + 1) * mx);
//            }
//        }
//        return f[n];
//    }
//};

//3144. 分割字符频率相等的最少子字符串

//给你一个字符串 s ，你需要将它分割成一个或者更多的 平衡 子字符串。比方说，s == "ababcc" 那么("abab", "c", "c") ，("ab", "abc", "c") 和("ababcc") 都是合法分割，
//但是("a", "bab", "cc") ，("aba", "bc", "c") 和("ab", "abcc") 不是，不平衡的子字符串用粗体表示。
//请你返回 s 最少 能分割成多少个平衡子字符串。
//注意：一个 平衡 字符串指的是字符串中所有字符出现的次数都相同。

//class Solution {
//public:
//    int minimumSubstringsInPartition(string s) {
//        int n = s.size();
//        vector<int> f(n + 1, INT_MAX);
//        f[0] = 0;
//        for (int i = 0; i < n; i++) {
//            int cnt[26]{}, k = 0, max_cnt = 0;
//            for (int j = i; j >= 0; j--) {
//                k += cnt[s[j] - 'a']++ == 0;
//                max_cnt = max(max_cnt, cnt[s[j] - 'a']);
//                if (i - j + 1 == k * max_cnt) {
//                    f[i + 1] = min(f[i + 1], f[j] + 1);
//                }
//            }
//        }
//        return f[n];
//    }
//};

//1416. 恢复数组

//某个程序本来应该输出一个整数数组。但是这个程序忘记输出空格了以致输出了一个数字字符串，我们所知道的信息只有：数组中所有整数都在[1, k] 之间，且数组中的数字都没有前导 0 。
//给你字符串 s 和整数 k 。可能会有多种不同的数组恢复结果。
//按照上述程序，请你返回所有可能输出字符串 s 的数组方案数。
//由于数组方案数可能会很大，请你返回它对 10 ^ 9 + 7 取余 后的结果。

//class Solution {
//    static constexpr int mod = 1'000'000'007;
//
//public:
//    int numberOfArrays(string s, int k) {
//        int len = 0;
//        int offset = k;
//        while (offset > 0) {
//            offset /= 10;
//            len++;
//        }
//        int n = s.size();
//        vector<int> dp(n + 1);
//        dp[0] = 1;
//        dp[1] = (s[0] != '0') && (s[0] - '0' <= k) ? 1 : 0;
//        long long step = 0;
//        long long cur_sum = 0;
//        for (int i = 1; i < n; i++) {
//            if (s[i] != '0' && (s[i] - '0' <= k))
//                dp[i + 1] = dp[i];
//            step = 10;
//            cur_sum = s[i] - '0';
//            for (int j = i - 1; j >= 0 && j >= i - len + 1; j--) {
//                cur_sum += (s[j] - '0') * step;
//                if (s[j] != '0' && cur_sum <= k) {
//                    dp[i + 1] = (dp[i + 1] + dp[j]) % mod;
//                }
//                step = (step * 10) % mod;
//            }
//        }
//        return dp[n];
//    }
//};

//2472. 不重叠回文子字符串的最大数目

//给你一个字符串 s 和一个 正 整数 k 。
//从字符串 s 中选出一组满足下述条件且 不重叠 的子字符串：
//每个子字符串的长度 至少 为 k 。
//每个子字符串是一个 回文串 。
//返回最优方案中能选择的子字符串的 最大 数目。
//子字符串 是字符串中一个连续的字符序列。

//class Solution {
//public:
//    int maxPalindromes(string s, int k) {
//        int n = s.size();
//        vector<int> f(n + 1);
//        for (int i = 0; i < 2 * n - 1; i++) {
//            int l = i / 2, r = (i + 1) / 2;
//            f[l + 1] = max(f[l + 1], f[l]);
//            for (; l >= 0 && r < n && s[l] == s[r]; l--, r++) {
//                if (r - l + 1 >= k) {
//                    f[r + 1] = max(f[r + 1], f[l] + 1);
//                    break;
//                }
//            }
//        }
//        return f[n];
//    }
//};

//1105. 填充书架

//给定一个数组 books ，其中 books[i] = [thicknessi, heighti] 表示第 i 本书的厚度和高度。你也会得到一个整数 shelfWidth 。
//按顺序 将这些书摆放到总宽度为 shelfWidth 的书架上。
//先选几本书放在书架上（它们的厚度之和小于等于书架的宽度 shelfWidth ），然后再建一层书架。重复这个过程，直到把所有的书都放在书架上。
//需要注意的是，在上述过程的每个步骤中，摆放书的顺序与给定图书数组 books 顺序相同。
//例如，如果这里有 5 本书，那么可能的一种摆放情况是：第一和第二本书放在第一层书架上，第三本书放在第二层书架上，第四和第五本书放在最后一层书架上。
//每一层所摆放的书的最大高度就是这一层书架的层高，书架整体的高度为各层高之和。
//以这种方式布置书架，返回书架整体可能的最小高度。

//class Solution {
//public:
//    int minHeightShelves(vector<vector<int>>& books, int shelf_width) {
//        int n = books.size(), f[n + 1];
//        f[0] = 0;
//        for (int i = 0; i < n; ++i) {
//            f[i + 1] = INT_MAX;
//            int max_h = 0, left_w = shelf_width;
//            for (int j = i; j >= 0; --j) {
//                left_w -= books[j][0];
//                if (left_w < 0) break; // 空间不足，无法放书
//                max_h = max(max_h, books[j][1]); // 从 j 到 i 的最大高度
//                f[i + 1] = min(f[i + 1], f[j] + max_h);
//            }
//        };
//        return f[n];
//    }
//};

//2547. 拆分数组的最小代价

//给你一个整数数组 nums 和一个整数 k 。
//将数组拆分成一些非空子数组。拆分的 代价 是每个子数组中的 重要性 之和。
//令 trimmed(subarray) 作为子数组的一个特征，其中所有仅出现一次的数字将会被移除。
//例如，trimmed([3, 1, 2, 4, 3, 4]) = [3, 4, 3, 4] 。
//子数组的 重要性 定义为 k + trimmed(subarray).length 。
//例如，如果一个子数组是[1, 2, 3, 3, 3, 4, 4] ，trimmed([1, 2, 3, 3, 3, 4, 4]) = [3, 3, 3, 4, 4] 。这个子数组的重要性就是 k + 5 。
//找出并返回拆分 nums 的所有可行方案中的最小代价。
//子数组 是数组的一个连续 非空 元素序列。

//class Solution {
//public:
//    int minCost(vector<int>& nums, int k) {
//        int n = nums.size(), f[n + 1];
//        f[0] = 0;
//        int8_t state[n];
//        for (int i = 0; i < n; ++i) {
//            memset(state, 0, sizeof(state));
//            int unique = 0, mn = INT_MAX;
//            for (int j = i; j >= 0; --j) {
//                int x = nums[j];
//                if (state[x] == 0) {
//                    state[x] = 1;
//                    ++unique;
//                }
//                else if (state[x] == 1) {
//                    state[x] = 2;
//                    --unique;
//                }
//                mn = min(mn, f[j] - unique);
//            }
//            f[i + 1] = k + mn;
//        }
//        return f[n] + n;
//    }
//};

//3578. 统计极差最大为 K 的分割方式数

//给你一个整数数组 nums 和一个整数 k。你的任务是将 nums 分割成一个或多个 非空 的连续子段，使得每个子段的 最大值 与 最小值 之间的差值 不超过 k。
//返回在此条件下将 nums 分割的总方法数。
//由于答案可能非常大，返回结果需要对 109 + 7 取余数。

//class Solution {
//public:
//    int countPartitions(vector<int>& nums, int k) {
//        const int MOD = 1'000'000'007;
//        int n = nums.size();
//        deque<int> min_q, max_q;
//        vector<int> f(n + 1);
//        f[0] = 1;
//        long long sum_f = 0; // 窗口中的 f[i] 之和
//        int left = 0;
//
//        for (int i = 0; i < n; i++) {
//            int x = nums[i];
//            // 1. 入
//            sum_f += f[i];
//
//            while (!min_q.empty() && x <= nums[min_q.back()]) {
//                min_q.pop_back();
//            }
//            min_q.push_back(i);
//
//            while (!max_q.empty() && x >= nums[max_q.back()]) {
//                max_q.pop_back();
//            }
//            max_q.push_back(i);
//
//            // 2. 出
//            while (nums[max_q.front()] - nums[min_q.front()] > k) {
//                sum_f -= f[left];
//                left++;
//                if (min_q.front() < left) {
//                    min_q.pop_front();
//                }
//                if (max_q.front() < left) {
//                    max_q.pop_front();
//                }
//            }
//            f[i + 1] = sum_f % MOD;
//        }
//
//        return f[n];
//    }
//};

//2430. 对字母串可执行的最大删除数

//给你一个仅由小写英文字母组成的字符串 s 。在一步操作中，你可以：
//删除 整个字符串 s ，或者
//对于满足 1 <= i <= s.length / 2 的任意 i ，如果 s 中的 前 i 个字母和接下来的 i 个字母 相等 ，删除 前 i 个字母。
//例如，如果 s = "ababc" ，那么在一步操作中，你可以删除 s 的前两个字母得到 "abc" ，因为 s 的前两个字母和接下来的两个字母都等于 "ab" 。
//返回删除 s 所需的最大操作数。

//class Solution {
//public:
//    int deleteString(string s) {
//        int n = s.size();
//        if (equal(s.begin() + 1, s.end(), s.begin())) {
//            return n;
//        }
//
//        vector lcp(n + 1, vector<int>(n + 1)); // lcp[i][j] 表示 s[i:] 和 s[j:] 的最长公共前缀
//        for (int i = n - 1; i >= 0; i--) {
//            for (int j = n - 1; j > i; j--) {
//                if (s[i] == s[j]) {
//                    lcp[i][j] = lcp[i + 1][j + 1] + 1;
//                }
//            }
//        }
//
//        vector<int> f(n);
//        for (int i = n - 1; i >= 0; i--) {
//            for (int j = 1; i + j * 2 <= n; j++) {
//                if (lcp[i][i + j] >= j) { // 说明 s[i:i+j] == s[i+j:i+j*2]
//                    f[i] = max(f[i], f[i + j]);
//                }
//            }
//            f[i]++;
//        }
//        return f[0];
//    }
//};

//2463. 最小移动总距离

//X 轴上有一些机器人和工厂。给你一个整数数组 robot ，其中 robot[i] 是第 i 个机器人的位置。
//再给你一个二维整数数组 factory ，其中 factory[j] = [positionj, limitj] ，表示第 j 个工厂的位置在 positionj ，且第 j 个工厂最多可以修理 limitj 个机器人。
//每个机器人所在的位置 互不相同 。每个工厂所在的位置也 互不相同 。注意一个机器人可能一开始跟一个工厂在 相同的位置 。
//所有机器人一开始都是坏的，他们会沿着设定的方向一直移动。设定的方向要么是 X 轴的正方向，要么是 X 轴的负方向。
//当一个机器人经过一个没达到上限的工厂时，这个工厂会维修这个机器人，且机器人停止移动。
//任何时刻，你都可以设置 部分 机器人的移动方向。你的目标是最小化所有机器人总的移动距离。
//请你返回所有机器人移动的最小总距离。测试数据保证所有机器人都可以被维修。
//注意：
//所有机器人移动速度相同。
//如果两个机器人移动方向相同，它们永远不会碰撞。
//如果两个机器人迎面相遇，它们也不会碰撞，它们彼此之间会擦肩而过。
//如果一个机器人经过了一个已经达到上限的工厂，机器人会当作工厂不存在，继续移动。
//机器人从位置 x 到位置 y 的移动距离为 | y - x | 。

//class Solution {
//public:
//    long long minimumTotalDistance(vector<int>& robot, vector<vector<int>>& factory) {
//        ranges::sort(factory, {}, [](auto& a) { return a[0]; });
//        ranges::sort(robot);
//        int m = robot.size();
//
//        vector<long long> f(m + 1, LLONG_MAX / 2);
//        f[0] = 0;
//        for (auto& fa : factory) {
//            for (int j = m; j > 0; j--) {
//                long long cost = 0;
//                for (int k = 1; k <= min(j, fa[1]); ++k) {
//                    cost += abs(robot[j - k] - fa[0]);
//                    f[j] = min(f[j], f[j - k] + cost);
//                }
//            }
//        }
//        return f[m];
//    }
//};

//3579. 字符串转换需要的最小操作数

//给你两个长度相等的字符串 word1 和 word2。你的任务是将 word1 转换成 word2。
//为此，可以将 word1 分割成一个或多个连续子字符串。对于每个子字符串 substr，可以执行以下操作：
//替换：将 substr 中任意一个索引处的字符替换为另一个小写字母。
//交换：交换 substr 中任意两个字符的位置。
//反转子串：将 substr 进行反转
//每种操作计为 一次 ，并且每个子串中的每个字符在每种操作中最多只能使用一次（即任何字符的下标不能参与超过一次替换、交换或反转操作）。
//返回将 word1 转换为 word2 所需的 最小操作数 。
//子串 是字符串中任意一个连续且非空的字符序列。

//class Solution {
//public:
//    int minOperations(string s, string t) {
//        int n = s.size();
//        vector<int> f(n + 1);
//        for (int i = 0; i < n; i++) {
//            int res = INT_MAX;
//            int cnt[26][26]{};
//            int op = 0;
//            for (int j = i; j >= 0; j--) {
//                // 不反转
//                int x = s[j] - 'a', y = t[j] - 'a';
//                if (x != y) {
//                    if (cnt[y][x] > 0) {
//                        cnt[y][x]--;
//                    }
//                    else {
//                        cnt[x][y]++;
//                        op++;
//                    }
//                }
//
//                // 反转
//                int rev_cnt[26][26]{};
//                int rev_op = 1;
//                for (int p = j; p <= i; p++) {
//                    char x = s[p] - 'a', y = t[i + j - p] - 'a';
//                    if (x == y) {
//                        continue;
//                    }
//                    if (rev_cnt[y][x] > 0) {
//                        rev_cnt[y][x]--;
//                    }
//                    else {
//                        rev_cnt[x][y]++;
//                        rev_op++;
//                    }
//                }
//
//                res = min(res, f[j] + min(op, rev_op));
//            }
//            f[i + 1] = res;
//        }
//        return f[n];
//    }
//};

//3500. 将数组分割为子数组的最小代价

//给你两个长度相等的整数数组 nums 和 cost，和一个整数 k。
//你可以将 nums 分割成多个子数组。第 i 个子数组由元素 nums[l..r] 组成，其代价为：
//(nums[0] + nums[1] + ... + nums[r] + k * i)* (cost[l] + cost[l + 1] + ... + cost[r])。
//注意，i 表示子数组的顺序：第一个子数组为 1，第二个为 2，依此类推。
//返回通过任何有效划分得到的 最小 总代价。
//子数组 是一个连续的 非空 元素序列。

//class Solution {
//public:
//    long long minimumCost(vector<int>& nums, vector<int>& cost, int k) {
//        int n = nums.size();
//        vector<int> s(n + 1);
//        partial_sum(cost.begin(), cost.end(), s.begin() + 1); // cost 的前缀和
//
//        vector<long long> f(n + 1, LLONG_MAX);
//        f[0] = 0;
//        int sum_num = 0;
//        for (int i = 1; i <= n; i++) {
//            sum_num += nums[i - 1];
//            for (int j = 0; j < i; j++) {
//                f[i] = min(f[i], f[j] + 1LL * sum_num * (s[i] - s[j]) + k * (s[n] - s[j]));
//            }
//        }
//        return f[n];
//    }
//};

//2977. 转换字符串的最小成本 II

//给你两个下标从 0 开始的字符串 source 和 target ，它们的长度均为 n 并且由 小写 英文字母组成。
//另给你两个下标从 0 开始的字符串数组 original 和 changed ，以及一个整数数组 cost ，其中 cost[i] 代表将字符串 original[i] 更改为字符串 changed[i] 的成本。
//你从字符串 source 开始。在一次操作中，如果 存在 任意 下标 j 满足 cost[j] == z  、original[j] == x 以及 changed[j] == y ，你就可以选择字符串中的 子串 x 并以 z 的成本将其更改为 y 。
//你可以执行 任意数量 的操作，但是任两次操作必须满足 以下两个 条件 之一 ：
//在两次操作中选择的子串分别是 source[a..b] 和 source[c..d] ，满足 b < c  或 d < a 。换句话说，两次操作中选择的下标 不相交 。
//在两次操作中选择的子串分别是 source[a..b] 和 source[c..d] ，满足 a == c 且 b == d 。换句话说，两次操作中选择的下标 相同 。
//返回将字符串 source 转换为字符串 target 所需的 最小 成本。如果不可能完成转换，则返回 - 1 。
//注意，可能存在下标 i 、j 使得 original[j] == original[i] 且 changed[j] == changed[i] 。

//struct Node {
//    Node* son[26]{};
//    int sid = -1; // 字符串的编号
//};
//
//class Solution {
//public:
//    long long minimumCost(string source, string target, vector<string>& original, vector<string>& changed, vector<int>& cost) {
//        Node* root = new Node();
//        int sid = 0;
//        auto put = [&](string& s) -> int {
//            Node* o = root;
//            for (char b : s) {
//                int i = b - 'a';
//                if (o->son[i] == nullptr) {
//                    o->son[i] = new Node();
//                }
//                o = o->son[i];
//            }
//            if (o->sid < 0) {
//                o->sid = sid++;
//            }
//            return o->sid;
//            };
//
//        // 初始化距离矩阵
//        int m = cost.size();
//        vector<vector<int>> dis(m * 2, vector<int>(m * 2, INT_MAX / 2));
//        for (int i = 0; i < m * 2; i++) {
//            dis[i][i] = 0;
//        }
//        for (int i = 0; i < m; i++) {
//            int x = put(original[i]);
//            int y = put(changed[i]);
//            dis[x][y] = min(dis[x][y], cost[i]);
//        }
//
//        // Floyd 求任意两点最短路
//        for (int k = 0; k < sid; k++) {
//            for (int i = 0; i < sid; i++) {
//                if (dis[i][k] == INT_MAX / 2) { // 加上这句话，巨大优化！
//                    continue;
//                }
//                for (int j = 0; j < sid; j++) {
//                    dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
//                }
//            }
//        }
//
//        int n = source.size();
//        vector<long long> memo(n, -1);
//        function<long long(int)> dfs = [&](int i) -> long long {
//            if (i >= n) {
//                return 0;
//            }
//            auto& res = memo[i];
//            if (res != -1) {
//                return res;
//            }
//            res = LONG_LONG_MAX / 2;
//            if (source[i] == target[i]) {
//                res = dfs(i + 1); // 不修改 source[i]
//            }
//            Node* p = root, * q = root;
//            for (int j = i; j < n; j++) {
//                p = p->son[source[j] - 'a'];
//                q = q->son[target[j] - 'a'];
//                if (p == nullptr || q == nullptr) {
//                    break;
//                }
//                if (p->sid < 0 || q->sid < 0) {
//                    continue;
//                }
//                // 修改从 i 到 j 的这一段
//                int d = dis[p->sid][q->sid];
//                if (d < INT_MAX / 2) {
//                    res = min(res, dis[p->sid][q->sid] + dfs(j + 1));
//                }
//            }
//            return res;
//            };
//        long long ans = dfs(0);
//        return ans < LONG_LONG_MAX / 2 ? ans : -1;
//    }
//};

//3441. 变成好标题的最少代价

//给你一个长度为 n 的字符串 caption 。如果字符串中 每一个 字符都位于连续出现 至少 3 次 的组中，那么我们称这个字符串是 好 标题。
//比方说：
//"aaabbb" 和 "aaaaccc" 都是 好 标题。
//"aabbb" 和 "ccccd" 都 不是 好标题。
//你可以对字符串执行以下操作 任意 次：
//选择一个下标 i（其中 0 <= i < n ）然后将该下标处的字符变为：
//该字符在字母表中 前 一个字母（前提是 caption[i] != 'a' ）
//该字符在字母表中 后 一个字母（caption[i] != 'z' ）
//你的任务是用 最少 操作次数将 caption 变为 好 标题。如果存在 多种 好标题，请返回它们中 字典序最小 的一个。如果 无法 得到好标题，请你返回一个空字符串 "" 。
//在字符串 a 和 b 中，如果两个字符串第一个不同的字符处，字符串 a 的字母比 b 的字母在字母表里出现的顺序更早，那么我们称字符串 a 的 字典序 比 b 小 。
//如果两个字符串前 min(a.length, b.length) 个字符都相同，那么较短的一个字符串字典序比另一个字符串小。

//class Solution {
//public:
//    string minCostGoodCaption(string s) {
//        int n = s.size();
//        if (n < 3) {
//            return "";
//        }
//
//        vector<array<int, 26>> f(n + 1);
//        vector<int> min_j(n + 1);
//        vector<array<int, 26>> nxt(n + 1);
//        for (int i = n - 1; i >= 0; i--) {
//            int mn = INT_MAX;
//            for (int j = 0; j < 26; j++) {
//                int res = f[i + 1][j] + abs(s[i] - 'a' - j);
//                int res2 = i <= n - 6 ? f[i + 3][min_j[i + 3]] + abs(s[i] - 'a' - j) + abs(s[i + 1] - 'a' - j) + abs(s[i + 2] - 'a' - j) : INT_MAX;
//                if (res2 < res || res2 == res && min_j[i + 3] < j) {
//                    res = res2;
//                    nxt[i][j] = min_j[i + 3]; // 记录转移来源
//                }
//                else {
//                    nxt[i][j] = j; // 记录转移来源
//                }
//                f[i][j] = res;
//                if (res < mn) {
//                    mn = res;
//                    min_j[i] = j; // 记录最小的 f[i][j] 中的 j 是多少
//                }
//            }
//        }
//
//        string ans(n, 0);
//        int i = 0, j = min_j[0];
//        while (i < n) {
//            ans[i] = 'a' + j;
//            int k = nxt[i][j];
//            if (k == j) {
//                i++;
//            }
//            else {
//                ans[i + 2] = ans[i + 1] = ans[i];
//                i += 3;
//                j = k;
//            }
//        }
//        return ans;
//    }
//};

//813. 最大平均值和的分组

//给定数组 nums 和一个整数 k 。我们将给定的数组 nums 分成 最多 k 个非空子数组，且数组内部是连续的 。 分数 由每个子数组内的平均值的总和构成。
//注意我们必须使用 nums 数组中的每一个数进行分组，并且分数不一定需要是整数。
//返回我们所能得到的最大 分数 是多少。答案误差在 10 - 6 内被视为是正确的。

//class Solution {
//public:
//    double largestSumOfAverages(vector<int>& nums, int k) {
//        int n = nums.size();
//        vector<double> prefix(n + 1);
//        for (int i = 0; i < n; i++) {
//            prefix[i + 1] = prefix[i] + nums[i];
//        }
//        vector<double> dp(n + 1);
//        for (int i = 1; i <= n; i++) {
//            dp[i] = prefix[i] / i;
//        }
//        for (int j = 2; j <= k; j++) {
//            for (int i = n; i >= j; i--) {
//                for (int x = j - 1; x < i; x++) {
//                    dp[i] = max(dp[i], dp[x] + (prefix[i] - prefix[x]) / (i - x));
//                }
//            }
//        }
//        return dp[n];
//    }
//};

//3599. 划分数组得到最小 XOR

//给你一个整数数组 nums 和一个整数 k。
//你的任务是将 nums 分成 k 个非空的 子数组 。对每个子数组，计算其所有元素的按位 XOR 值。
//返回这 k 个子数组中 最大 XOR 的 最小值 。
//子数组 是数组中连续的 非空 元素序列。

//class Solution {
//public:
//    int minXor(vector<int>& nums, int k) {
//        int n = nums.size();
//        vector f(k + 1, vector<int>(n + 1, INT_MAX));
//        f[0][0] = 0;
//        for (int i = 1; i <= k; i++) {
//            // 前后每个子数组长度至少是 1，预留空间给这些子数组
//            for (int j = i; j <= n - (k - i); j++) {
//                int s = 0;
//                // 枚举所有分割方案，取最小值
//                for (int l = j - 1; l >= i - 1; l--) {
//                    s ^= nums[l];
//                    // 对于单个分割方案，子数组异或和要取最大值
//                    f[i][j] = min(f[i][j], max(f[i - 1][l], s));
//                }
//            }
//        }
//        return f[k][n];
//    }
//};

//410. 分割数组的最大值

//给定一个非负整数数组 nums 和一个整数 k ，你需要将这个数组分成 k 个非空的连续子数组，使得这 k 个子数组各自和的最大值 最小。
//返回分割后最小的和的最大值。
//子数组 是数组中连续的部份。

//class Solution {
//public:
//    int splitArray(vector<int>& nums, int k) {
//        auto check = [&](int mx) -> bool {
//            int cnt = 1, s = 0;
//            for (int x : nums) {
//                if (s + x <= mx) {
//                    s += x;
//                    continue;
//                }
//                if (cnt == k) { // 不能继续划分
//                    return false;
//                }
//                cnt++; // 新划分一段
//                s = x;
//            }
//            return true;
//            };
//
//        int left = ranges::max(nums) - 1;
//        int right = reduce(nums.begin(), nums.end());
//        while (left + 1 < right) {
//            int mid = left + (right - left) / 2;
//            (check(mid) ? right : left) = mid;
//        }
//        return right;
//    }
//};

//1278. 分割回文串 III

//给你一个由小写字母组成的字符串 s，和一个整数 k。
//请你按下面的要求分割字符串：
//首先，你可以将 s 中的部分字符修改为其他的小写英文字母。
//接着，你需要把 s 分割成 k 个非空且不相交的子串，并且每个子串都是回文串。
//请返回以这种方式分割字符串所需修改的最少字符数。

//class Solution {
//public:
//    int palindromePartition(string s, int k) {
//        int n = s.size();
//        vector min_change(n, vector<int>(n));
//        for (int i = n - 2; i >= 0; i--) {
//            for (int j = i + 1; j < n; j++) {
//                min_change[i][j] = min_change[i + 1][j - 1] + (s[i] != s[j] ? 1 : 0);
//            }
//        }
//
//        vector f(k, vector<int>(n, INT_MAX));
//        f[0] = move(min_change[0]);
//        for (int i = 1; i < k; i++) {
//            for (int r = i; r <= n - k + i; r++) {
//                for (int l = i; l <= r; l++) {
//                    f[i][r] = min(f[i][r], f[i - 1][l - 1] + min_change[l][r]);
//                }
//            }
//        }
//        return f[k - 1][n - 1];
//    }
//};

//1745. 分割回文串 IV

//给你一个字符串 s ，如果可以将它分割成三个 非空 回文子字符串，那么返回 true ，否则返回 false 。
//当一个字符串正着读和反着读是一模一样的，就称其为 回文字符串 。

//class Solution {
//    // 1278. 分割回文串 III
//    int palindromePartition(string& s, int k) {
//        int n = s.size();
//        vector min_change(n, vector<int>(n));
//        for (int i = n - 2; i >= 0; i--) {
//            for (int j = i + 1; j < n; j++) {
//                min_change[i][j] = min_change[i + 1][j - 1] + (s[i] != s[j] ? 1 : 0);
//            }
//        }
//
//        auto f = move(min_change[0]);
//        for (int i = 1; i < k; i++) {
//            for (int r = n - k + i; r >= i; r--) {
//                f[r] = INT_MAX;
//                for (int l = i; l <= r; l++) {
//                    f[r] = min(f[r], f[l - 1] + min_change[l][r]);
//                }
//            }
//        }
//        return f[n - 1];
//    }
//
//public:
//    bool checkPartitioning(string s) {
//        return palindromePartition(s, 3) == 0;
//    }
//};

//1335. 工作计划的最低难度

//你需要制定一份 d 天的工作计划表。工作之间存在依赖，要想执行第 i 项工作，你必须完成全部 j 项工作（ 0 <= j < i）。
//你每天 至少 需要完成一项任务。工作计划的总难度是这 d 天每一天的难度之和，而一天的工作难度是当天应该完成工作的最大难度。
//给你一个整数数组 jobDifficulty 和一个整数 d，分别代表工作难度和需要计划的天数。第 i 项工作的难度是 jobDifficulty[i]。
//返回整个工作计划的 最小难度 。如果无法制定工作计划，则返回 - 1 。

//class Solution {
//public:
//    int minDifficulty(vector<int>& a, int d) {
//        int n = a.size();
//        if (n < d) return -1;
//
//        int f[d][n];
//        f[0][0] = a[0];
//        for (int i = 1; i < n; i++)
//            f[0][i] = max(f[0][i - 1], a[i]);
//        for (int i = 1; i < d; i++) {
//            for (int j = n - 1; j >= i; j--) {
//                f[i][j] = INT_MAX;
//                int mx = 0;
//                for (int k = j; k >= i; k--) {
//                    mx = max(mx, a[k]); // 从 a[k] 到 a[j] 的最大值
//                    f[i][j] = min(f[i][j], f[i - 1][k - 1] + mx);
//                }
//            }
//        }
//        return f[d - 1][n - 1];
//    }
//};

//1473. 粉刷房子 III

//在一个小城市里，有 m 个房子排成一排，你需要给每个房子涂上 n 种颜色之一（颜色编号为 1 到 n ）。有的房子去年夏天已经涂过颜色了，所以这些房子不可以被重新涂色。
//我们将连续相同颜色尽可能多的房子称为一个街区。（比方说 houses = [1, 2, 2, 3, 3, 2, 1, 1] ，它包含 5 个街区[{1}, { 2,2 }, { 3,3 }, { 2 }, { 1,1 }] 。）
//给你一个数组 houses ，一个 m* n 的矩阵 cost 和一个整数 target ，其中：
//houses[i]：是第 i 个房子的颜色，0 表示这个房子还没有被涂色。
//cost[i][j]：是将第 i 个房子涂成颜色 j + 1 的花费。
//请你返回房子涂色方案的最小总花费，使得每个房子都被涂色后，恰好组成 target 个街区。如果没有可用的涂色方案，请返回 - 1 。

//class Solution {
//private:
//    static constexpr int INFTY = INT_MAX / 2;
//
//public:
//    int minCost(vector<int>& houses, vector<vector<int>>& cost, int m, int n, int target) {
//        // 将颜色调整为从 0 开始编号，没有被涂色标记为 -1
//        for (int& c : houses) {
//            --c;
//        }
//
//        // dp 所有元素初始化为极大值
//        vector<vector<vector<int>>> dp(m, vector<vector<int>>(n, vector<int>(target, INFTY)));
//
//        for (int i = 0; i < m; ++i) {
//            for (int j = 0; j < n; ++j) {
//                if (houses[i] != -1 && houses[i] != j) {
//                    continue;
//                }
//
//                for (int k = 0; k < target; ++k) {
//                    for (int j0 = 0; j0 < n; ++j0) {
//                        if (j == j0) {
//                            if (i == 0) {
//                                if (k == 0) {
//                                    dp[i][j][k] = 0;
//                                }
//                            }
//                            else {
//                                dp[i][j][k] = min(dp[i][j][k], dp[i - 1][j][k]);
//                            }
//                        }
//                        else if (i > 0 && k > 0) {
//                            dp[i][j][k] = min(dp[i][j][k], dp[i - 1][j0][k - 1]);
//                        }
//                    }
//
//                    if (dp[i][j][k] != INFTY && houses[i] == -1) {
//                        dp[i][j][k] += cost[i][j];
//                    }
//                }
//            }
//        }
//
//        int ans = INFTY;
//        for (int j = 0; j < n; ++j) {
//            ans = min(ans, dp[m - 1][j][target - 1]);
//        }
//        return ans == INFTY ? -1 : ans;
//    }
//};

//2209. 用地毯覆盖后的最少白色砖块

//给你一个下标从 0 开始的 二进制 字符串 floor ，它表示地板上砖块的颜色。
//floor[i] = '0' 表示地板上第 i 块砖块的颜色是 黑色 。
//floor[i] = '1' 表示地板上第 i 块砖块的颜色是 白色 。
//同时给你 numCarpets 和 carpetLen 。你有 numCarpets 条 黑色 的地毯，每一条 黑色 的地毯长度都为 carpetLen 块砖块。
//请你使用这些地毯去覆盖砖块，使得未被覆盖的剩余 白色 砖块的数目 最小 。地毯相互之间可以覆盖。
//请你返回没被覆盖的白色砖块的 最少 数目。

//class Solution {
//public:
//    int minimumWhiteTiles(string floor, int numCarpets, int carpetLen) {
//        int m = floor.size();
//        vector f(numCarpets + 1, vector<int>(m));
//        // 单独计算 i=0 的情况，本质是 floor 的前缀和
//        f[0][0] = floor[0] - '0';
//        for (int j = 1; j < m; j++) {
//            f[0][j] = f[0][j - 1] + (floor[j] - '0');
//        }
//        for (int i = 1; i <= numCarpets; i++) {
//            for (int j = carpetLen * i; j < m; j++) {
//                f[i][j] = min(f[i][j - 1] + (floor[j] - '0'), f[i - 1][j - carpetLen]);
//            }
//        }
//        return f[numCarpets][m - 1];
//    }
//};

//1478. 安排邮筒

//给你一个房屋数组houses 和一个整数 k ，其中 houses[i] 是第 i 栋房子在一条街上的位置，现需要在这条街上安排 k 个邮筒。
//请你返回每栋房子与离它最近的邮筒之间的距离的 最小 总和。
//答案保证在 32 位有符号整数范围以内。

//class Solution {
//public:
//    int minDistance(vector<int>& houses, int k) {
//        int n = houses.size();
//        ranges::sort(houses);
//
//        vector<vector<int>> medsum(n, vector<int>(n));
//        for (int i = n - 2; i >= 0; --i) {
//            for (int j = i + 1; j < n; ++j) {
//                medsum[i][j] = medsum[i + 1][j - 1] + houses[j] - houses[i];
//            }
//        }
//
//        vector<vector<int>> f(n, vector<int>(k + 1, INT_MAX / 2));
//        for (int i = 0; i < n; ++i) {
//            f[i][1] = medsum[0][i];
//            for (int j = 2; j <= k && j <= i + 1; ++j) {
//                for (int i0 = 0; i0 < i; ++i0) {
//                    f[i][j] = min(f[i][j], f[i0][j - 1] + medsum[i0 + 1][i]);
//                }
//            }
//        }
//
//        return f[n - 1][k];
//    }
//};

//3473. 长度至少为 M 的 K 个子数组之和

//给你一个整数数组 nums 和两个整数 k 和 m。
//返回数组 nums 中 k 个不重叠子数组的 最大 和，其中每个子数组的长度 至少 为 m。
//子数组 是数组中的一个连续序列。

//class Solution {
//public:
//    int maxSum(vector<int>& nums, int k, int m) {
//        int n = nums.size();
//        vector<int> s(n + 1);
//        partial_sum(nums.begin(), nums.end(), s.begin() + 1); // nums 的前缀和
//
//        vector f(k + 1, vector<int>(n + 1));
//        for (int i = 1; i <= k; i++) {
//            f[i][i * m - 1] = INT_MIN;
//            int mx = INT_MIN;
//            // 左右两边留出足够空间给其他子数组
//            for (int j = i * m; j <= n - (k - i) * m; j++) {
//                // mx 表示最大的 f[i-1][L]-s[L]，其中 L 在区间 [(i-1)*m, j-m] 中
//                mx = max(mx, f[i - 1][j - m] - s[j - m]);
//                f[i][j] = max(f[i][j - 1], mx + s[j]); // 不选 vs 选
//            }
//        }
//        return f[k][n];
//    }
//};

//1959. K 次调整数组大小浪费的最小总空间

//你正在设计一个动态数组。给你一个下标从 0 开始的整数数组 nums ，其中 nums[i] 是 i 时刻数组中的元素数目。
//除此以外，你还有一个整数 k ，表示你可以 调整 数组大小的 最多 次数（每次都可以调整成 任意 大小）。
//t 时刻数组的大小 sizet 必须大于等于 nums[t] ，因为数组需要有足够的空间容纳所有元素。
//t 时刻 浪费的空间 为 sizet - nums[t] ，总 浪费空间为满足 0 <= t < nums.length 的每一个时刻 t 浪费的空间 之和 。
//在调整数组大小不超过 k 次的前提下，请你返回 最小总浪费空间 。
//注意：数组最开始时可以为 任意大小 ，且 不计入 调整大小的操作次数。

//class Solution {
//public:
//    int minSpaceWastedKResizing(vector<int>& nums, int k) {
//        int n = nums.size();
//
//        // 预处理数组 g
//        vector<vector<int>> g(n, vector<int>(n));
//        for (int i = 0; i < n; ++i) {
//            // 记录子数组的最大值
//            int best = INT_MIN;
//            // 记录子数组的和
//            int total = 0;
//            for (int j = i; j < n; ++j) {
//                best = max(best, nums[j]);
//                total += nums[j];
//                g[i][j] = best * (j - i + 1) - total;
//            }
//        }
//
//        vector<vector<int>> f(n, vector<int>(k + 2, INT_MAX / 2));
//        for (int i = 0; i < n; ++i) {
//            for (int j = 1; j <= k + 1; ++j) {
//                for (int i0 = 0; i0 <= i; ++i0) {
//                    f[i][j] = min(f[i][j], (i0 == 0 ? 0 : f[i0 - 1][j - 1]) + g[i0][i]);
//                }
//            }
//        }
//
//        return f[n - 1][k + 1];
//    }
//};

//2478. 完美分割的方案数

//给你一个字符串 s ，每个字符是数字 '1' 到 '9' ，再给你两个整数 k 和 minLength 。
//如果对 s 的分割满足以下条件，那么我们认为它是一个 完美 分割：
//s 被分成 k 段互不相交的子字符串。
//每个子字符串长度都 至少 为 minLength 。
//每个子字符串的第一个字符都是一个 质数 数字，最后一个字符都是一个 非质数 数字。质数数字为 '2' ，'3' ，'5' 和 '7' ，剩下的都是非质数数字。
//请你返回 s 的 完美 分割数目。由于答案可能很大，请返回答案对 109 + 7 取余 后的结果。
//一个 子字符串 是字符串中一段连续字符串序列。

//class Solution {
//    const int MOD = 1e9 + 7;
//
//    bool is_prime(char c) {
//        return c == '2' || c == '3' || c == '5' || c == '7';
//    }
//
//    // 判断是否可以在 j-1 和 j 之间分割（开头和末尾也算）
//    bool can_partition(string& s, int j) {
//        return j == 0 || j == s.length() || !is_prime(s[j - 1]) && is_prime(s[j]);
//    }
//
//public:
//    int beautifulPartitions(string& s, int k, int l) {
//        int n = s.length();
//        if (k * l > n || !is_prime(s[0]) || is_prime(s[n - 1])) // 剪枝
//            return 0;
//        int f[k + 1][n + 1]; memset(f, 0, sizeof(f));
//        f[0][0] = 1;
//        for (int i = 1; i <= k; ++i) {
//            int sum = 0;
//            for (int j = i * l; j + (k - i) * l <= n; j++) {
//                if (can_partition(s, j - l)) sum = (sum + f[i - 1][j - l]) % MOD; // j'=j-l 双指针
//                if (can_partition(s, j)) f[i][j] = sum;
//            }
//        }
//        return f[k][n];
//    }
//};

//3538. 合并得到最小旅行时间

//给你一个长度为 l 公里的直路，一个整数 n，一个整数 k 和 两个 长度为 n 的整数数组 position 和 time 。
//数组 position 列出了路标的位置（单位：公里），并且是 严格 升序排列的（其中 position[0] = 0 且 position[n - 1] = l）。
//每个 time[i] 表示从 position[i] 到 position[i + 1] 之间行驶 1 公里所需的时间（单位：分钟）。
//你 必须 执行 恰好 k 次合并操作。在一次合并中，你可以选择两个相邻的路标，下标为 i 和 i + 1（其中 i > 0 且 i + 1 < n），并且：
//更新索引为 i + 1 的路标，使其时间变为 time[i] + time[i + 1]。
//删除索引为 i 的路标。
//返回经过 恰好 k 次合并后从 0 到 l 的 最小总旅行时间（单位：分钟）。

//class Solution {
//public:
//    int minTravelTime(int, int n, int K, vector<int>& position, vector<int>& time) {
//        vector<int> s(n); // time 的前缀和
//        partial_sum(time.begin(), time.end() - 1, s.begin() + 1); // time[n-1] 用不到
//
//        vector f(n, vector(K + 1, vector<int>(K + 1, INT_MAX / 2)));
//        for (int sz = 0; sz <= K; sz++) {
//            f[n - 1][sz][0] = 0;
//        }
//        for (int j = n - 2; j >= 0; j--) { // 转移来源 k 比 j 大，所以要倒序
//            for (int sz = 0; sz <= min(K, j); sz++) {
//                int t = s[j + 1] - s[j - sz]; // 合并到 time[j] 的时间
//                for (int left_k = 0; left_k <= min(K, n - 2 - j); left_k++) {
//                    int res = INT_MAX;
//                    // 枚举下一个子数组 [j+1, k]
//                    for (int k = j + 1; k <= j + 1 + left_k; k++) {
//                        int r = f[k][k - j - 1][left_k - (k - j - 1)] + (position[k] - position[j]) * t;
//                        res = min(res, r);
//                    }
//                    f[j][sz][left_k] = res;
//                }
//            }
//        }
//        return f[0][0][K]; // 第一个子数组是 [0, 0]
//    }
//};

//3505. 使 K 个子数组内元素相等的最少操作数

//给你一个整数数组 nums 和两个整数 x 和 k。你可以执行以下操作任意次（包括零次）：
//将 nums 中的任意一个元素加 1 或减 1。
//返回为了使 nums 中 至少 包含 k 个长度 恰好 为 x 的不重叠子数组（每个子数组中的所有元素都相等）所需要的 最少 操作数。
//子数组 是数组中连续、非空的一段元素。

//template<typename T, typename Compare = less<T>>
//class LazyHeap {
//    priority_queue<T, vector<T>, Compare> pq;
//    unordered_map<T, int> remove_cnt; // 每个元素剩余需要删除的次数
//    size_t sz = 0; // 实际大小
//    long long s = 0; // 堆中元素总和
//
//    // 正式执行删除操作
//    void apply_remove() {
//        while (!pq.empty() && remove_cnt[pq.top()] > 0) {
//            remove_cnt[pq.top()]--;
//            pq.pop();
//        }
//    }
//
//public:
//    size_t size() {
//        return sz;
//    }
//
//    long long sum() {
//        return s;
//    }
//
//    // 删除
//    void remove(T x) {
//        remove_cnt[x]++; // 懒删除
//        sz--;
//        s -= x;
//    }
//
//    // 查看堆顶
//    T top() {
//        apply_remove();
//        return pq.top();
//    }
//
//    // 出堆
//    T pop() {
//        apply_remove();
//        T x = pq.top();
//        pq.pop();
//        sz--;
//        s -= x;
//        return x;
//    }
//
//    // 入堆
//    void push(T x) {
//        if (remove_cnt[x] > 0) {
//            remove_cnt[x]--; // 抵消之前的删除
//        }
//        else {
//            pq.push(x);
//        }
//        sz++;
//        s += x;
//    }
//
//    // push(x) 然后 pop()
//    T push_pop(T x) {
//        apply_remove();
//        pq.push(x);
//        s += x;
//        x = pq.top();
//        pq.pop();
//        s -= x;
//        return x;
//    }
//};
//
//class Solution {
//    // 480. 滑动窗口中位数（有改动）
//    // 返回 nums 的所有长为 k 的子数组的（到子数组中位数的）距离和
//    vector<long long> medianSlidingWindow(vector<int>& nums, int k) {
//        int n = nums.size();
//        vector<long long> ans(n - k + 1);
//        LazyHeap<int> left; // 最大堆
//        LazyHeap<int, greater<int>> right; // 最小堆
//
//        for (int i = 0; i < n; i++) {
//            // 1. 进入窗口
//            int in = nums[i];
//            if (left.size() == right.size()) {
//                left.push(right.push_pop(in));
//            }
//            else {
//                right.push(left.push_pop(in));
//            }
//
//            int l = i + 1 - k;
//            if (l < 0) { // 窗口大小不足 k
//                continue;
//            }
//
//            // 2. 计算答案
//            long long v = left.top();
//            long long s1 = v * left.size() - left.sum();
//            long long s2 = right.sum() - v * right.size();
//            ans[l] = s1 + s2;
//
//            // 3. 离开窗口
//            int out = nums[l];
//            if (out <= left.top()) {
//                left.remove(out);
//                if (left.size() < right.size()) {
//                    left.push(right.pop()); // 平衡两个堆的大小
//                }
//            }
//            else {
//                right.remove(out);
//                if (left.size() > right.size() + 1) {
//                    right.push(left.pop()); // 平衡两个堆的大小
//                }
//            }
//        }
//
//        return ans;
//    }
//
//public:
//    long long minOperations(vector<int>& nums, int x, int k) {
//        int n = nums.size();
//        vector<long long> dis = medianSlidingWindow(nums, x);
//        vector f(k + 1, vector<long long>(n + 1));
//        for (int i = 1; i <= k; i++) {
//            f[i][i * x - 1] = LLONG_MAX;
//            for (int j = i * x; j <= n - (k - i) * x; j++) { // 左右留出足够空间给其他子数组
//                f[i][j] = min(f[i][j - 1], f[i - 1][j - x] + dis[j - x]); // j-x 为子数组左端点
//            }
//        }
//        return f[k][n];
//    }
//};

//3077. K 个不相交子数组的最大能量值

//给你一个长度为 n 下标从 0 开始的整数数组 nums 和一个 正奇数 整数 k 。
//x 个子数组的能量值定义为 strength = sum[1] * x - sum[2] * (x - 1) + sum[3] * (x - 2) - sum[4] * (x - 3) + ... + sum[x] * 1 ，其中 sum[i] 是第 i 个子数组的和。
//更正式的，能量值是满足 1 <= i <= x 的所有 i 对应的(-1)i + 1 * sum[i] * (x - i + 1) 之和。
//你需要在 nums 中选择 k 个 不相交子数组 ，使得 能量值最大 。
//请你返回可以得到的 最大能量值 。
//注意，选出来的所有子数组 不 需要覆盖整个数组。

//class Solution {
//public:
//    long long maximumStrength(vector<int>& nums, int k) {
//        int n = nums.size();
//        vector<long long> s(n + 1);
//        for (int i = 0; i < n; i++) {
//            s[i + 1] = s[i] + nums[i];
//        }
//        vector<vector<long long>> f(k + 1, vector<long long>(n + 1));
//        for (int i = 1; i <= k; i++) {
//            f[i][i - 1] = LLONG_MIN;
//            long long mx = LLONG_MIN;
//            int w = (k - i + 1) * (i % 2 ? 1 : -1);
//            // j 不能太小也不能太大，要给前面留 i-1 个数，后面留 k-i 个数
//            for (int j = i; j <= n - k + i; j++) {
//                mx = max(mx, f[i - 1][j - 1] - s[j - 1] * w);
//                f[i][j] = max(f[i][j - 1], s[j] * w + mx);
//            }
//        }
//        return f[k][n];
//    }
//};

//2911. 得到 K 个半回文串的最少修改次数

//给你一个字符串 s 和一个整数 k ，请你将 s 分成 k 个 子字符串 ，使得每个 子字符串 变成 半回文串 需要修改的字符数目最少。
//请你返回一个整数，表示需要修改的 最少 字符数目。
//注意：
//如果一个字符串从左往右和从右往左读是一样的，那么它是一个 回文串 。
//如果长度为 len 的字符串存在一个满足 1 <= d < len 的正整数 d ，len % d == 0 成立且所有对 d 做除法余数相同的下标对应的字符连起来得到的字符串都是 回文串 ，那么我们说这个字符串是 半回文串 
//比方说 "aa" ，"aba" ，"adbgad" 和 "abab" 都是 半回文串 ，而 "a" ，"ab" 和 "abca" 不是。
//子字符串 指的是一个字符串中一段连续的字符序列。

//const int MX = 201;
//vector<int> divisors[MX];
//
//int init = [] {
//    for (int i = 1; i < MX; i++) {
//        for (int j = i * 2; j < MX; j += i) {
//            divisors[j].push_back(i);
//        }
//    }
//    return 0;
//    }();
//
//class Solution {
//    int get_modify(const string& s, int begin, int end) {
//        int n = end - begin;
//        int res = n;
//        for (int d : divisors[n]) {
//            int cnt = 0;
//            for (int i0 = 0; i0 < d; i0++) {
//                for (int i = begin + i0, j = end - d + i0; i < j; i += d, j -= d) {
//                    cnt += s[i] != s[j];
//                }
//            }
//            res = min(res, cnt);
//        }
//        return res;
//    }
//
//public:
//    int minimumChanges(string s, int k) {
//        int n = s.length();
//        vector<vector<int>> modify(n - 1, vector<int>(n));
//        for (int left = 0; left < n - 1; left++) {
//            for (int right = left + 1; right < n; right++) {
//                modify[left][right] = get_modify(s, left, right + 1);
//            }
//        }
//
//        vector<int> f(modify[0]);
//        for (int i = 1; i < k; i++) {
//            for (int j = n - 1 - (k - 1 - i) * 2; j > i * 2; j--) { 
//                f[j] = INT_MAX;
//                for (int L = i * 2; L < j; L++) {
//                    f[j] = min(f[j], f[L - 1] + modify[L][j]);
//                }
//            }
//        }
//        return f[n - 1];
//    }
//};

//3117. 划分数组得到最小的值之和

//给你两个数组 nums 和 andValues，长度分别为 n 和 m。
//数组的 值 等于该数组的 最后一个 元素。
//你需要将 nums 划分为 m 个 不相交的连续 子数组，对于第 ith 个子数组[li, ri]，子数组元素的按位 AND 运算结果等于 andValues[i]，换句话说，
//对所有的 1 <= i <= m，nums[li] & nums[li + 1] & ... & nums[ri] == andValues[i] ，其中 & 表示按位 AND 运算符。
//返回将 nums 划分为 m 个子数组所能得到的可能的 最小 子数组 值 之和。如果无法完成这样的划分，则返回 - 1 。

//class Solution {
//public:
//    int minimumValueSum(vector<int>& nums, vector<int>& andValues) {
//        const int INF = 0x3f3f3f3f;
//        int n = nums.size();
//        vector<int> f(n + 1, INF);
//        vector<int> new_f(n + 1);
//
//        f[0] = 0;
//        for (int target : andValues) {
//            auto a = nums;
//            int left = 0, right = 0;
//            deque<int> q; // 单调队列，保存 f 的下标
//            int qi = 0; // 单调队列目前处理到 f[qi]
//
//            new_f[0] = INF;
//            for (int i = 0; i < n; i++) {
//                int x = a[i];
//                for (int j = i - 1; j >= 0 && (a[j] & x) != a[j]; j--) {
//                    a[j] &= x;
//                }
//                while (left <= i && a[left] < target) {
//                    left++;
//                }
//                while (right <= i && a[right] <= target) {
//                    right++;
//                }
//
//                // 上面这段的目的是求出子数组右端点为 i 时，子数组左端点的最小值和最大值+1
//                // 下面是单调队列的滑窗过程
//
//                if (left < right) {
//                    // 单调队列：右边入
//                    for (; qi < right; qi++) {
//                        while (!q.empty() && f[qi] <= f[q.back()]) {
//                            q.pop_back();
//                        }
//                        q.push_back(qi);
//                    }
//
//                    // 单调队列：左边出
//                    while (q.front() < left) {
//                        q.pop_front();
//                    }
//
//                    // 单调队列：计算答案
//                    new_f[i + 1] = f[q.front()] + x; // 队首就是最小值
//                }
//                else {
//                    new_f[i + 1] = INF;
//                }
//            }
//            swap(f, new_f);
//        }
//        return f[n] < INF ? f[n] : -1;
//    }
//};